競プロ典型90問 009 Three Point Angle(★6)
まず,
真ん中を固定する
. ここで角を作る真ん中の点を原点としてすべての点を平行移動させた座標平面を考える. まず, 各点を偏角ソートしておく. 偏角ソートについては
この記事
を参考にしてほしい. なお, 今回はラジアンではなく度数法で表現しソートした. あとは典型的な二分探索(偏角同士のなす角の大きさが180度に近くなるような点を選ぶ)をすることにより, この問題を
$ O(N^2 \log N)
で解くことができる.
実装例:
https://atcoder.jp/contests/typical90/submissions/24974571